class Allocator
{
public:
    Allocator(int n)
    {
        total = n;
        spaces[0] = n;
    }

    int allocate(int size, int mID)
    {
        int position = -1;
        for (auto &[spacePos, spaceSize] : spaces)
        {
            if (spaceSize >= size)
            {
                position = spacePos;
                break;
            }
        }
        if (position == -1)
        {
            return -1;
        }
        idPositions[mID].push_back(position);
        spaces[position + size] = spaces[position] - size;
        spaces.erase(position);
        used[position] = size;
        return position;
    }

    int free(int mID)
    {
        int freedSize = 0;
        for (int position : idPositions[mID])
        {
            int partFreeSize = used[position];
            freedSize += partFreeSize;
            used.erase(position);
            spaces[position] = partFreeSize;
            if (spaces.count(position + partFreeSize))
            {
                spaces[position] += spaces[position + partFreeSize];
                spaces.erase(position + partFreeSize);
            }
            auto curIt = spaces.find(position);
            if (curIt != spaces.begin())
            {
                --curIt;
                int lastPos = curIt->first;
                int lastSpaceSize = curIt->second;
                if (position == lastPos + lastSpaceSize)
                {
                    spaces[lastPos] += spaces[position];
                    spaces.erase(position);
                }
            }
        }
        idPositions.erase(mID);
        return freedSize;
    }

private:
    map<int, int> spaces;
    unordered_map<int, int> used;
    unordered_map<int, vector<int>> idPositions;
    int total;
};

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator* obj = new Allocator(n);
 * int param_1 = obj->allocate(size,mID);
 * int param_2 = obj->free(mID);
 */